package com.demo.链表.chenglei;

import cn.hutool.core.lang.Console;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * @author cl
 */
public class Linked01 {

    public static void main(String[] args) {
        LinkedNode<Integer> head = createRandomLinked();
        printRandomLinked(head);
        // 随机链表的copy
        // 1. 使用HashMap存储键值对
        Console.log("通过使用HashMap存储键值对结果:");
        printRandomLinked(cloneByMap(head));
        printRandomLinked(head);
        // 2. 原地复制
        Console.log("通过原地复制结果:");
        printRandomLinked(cloneByLinked(head));
        printRandomLinked(head);
    }

    private static <T> LinkedNode<T> cloneByMap(LinkedNode<T> head) {
        if (head == null) {
            return null;
        }
        Map<LinkedNode<T>, LinkedNode<T>> tmpMap = new HashMap<>();
        LinkedNode<T> current = head;
        while (current != null) {
            LinkedNode<T> node = new LinkedNode<>();
            node.data = current.data;
            tmpMap.put(current, node);
            current = current.next;
        }

        current = head;
        while (current != null) {
            tmpMap.get(current).next = tmpMap.get(current.next);
            tmpMap.get(current).random = current.random != null ? tmpMap.get(current.random) : null;
            current = current.next;
        }
        return tmpMap.get(head);
    }

    private static <T> LinkedNode<T> cloneByLinked(LinkedNode<T> head) {
        if (head == null) {
            return null;
        }
        // 通过克隆节点方式
        // 1->2->3->4 => 1->1`->2->2`->3->3`->4->4`
        LinkedNode<T> current = head;
        while (current != null) {
            // 克隆 ` 节点
            LinkedNode<T> tmp = new LinkedNode<>();
            tmp.data = current.data;
            // 节点追加
            tmp.next = current.next;
            current.next = tmp;
            current = tmp.next;
        }
        // 随机指针赋值
        current = head;
        while (current != null) {
            // current.next ` 节点
            current.next.random = current.random != null ? current.random.next : null;
            // current.next 一定不为null
            current = current.next.next;
        }
        // 还原原始链表，即分离原链表和克隆链表
        current = head;
        LinkedNode<T> cloneHead = current.next;
        while (current.next != null) {
            LinkedNode<T> t = current.next;
            current.next = current.next.next;
            current = t;
        }
        return cloneHead;
    }

    private static LinkedNode<Integer> createRandomLinked() {
        // 创建一个含有随机指针的链表
        Integer[] data = new Integer[]{1, 2, 3, 4, 5, 6, 7, 8};
        ArrayList<LinkedNode<Integer>> tmp = new ArrayList<>();
        LinkedNode<Integer> head = null;
        LinkedNode<Integer> tail = null;
        for (Integer d : data) {
            LinkedNode<Integer> node = new LinkedNode<>();
            node.data = d;
            if (head == null) {
                head = node;
                tail = node;
            } else {
                tail.next = node;
                tail = node;
            }
            tmp.add(node);
        }
        for (int i = 0; i < Math.random() * data.length; i ++) {
            int index = (int) (Math.random() * data.length);
            LinkedNode<Integer> t = tmp.get(index);
            if (t.random == null) {
                index = (int) (Math.random() * data.length);
                LinkedNode<Integer> t0 = tmp.get(index);
                t.random = t0;
            }
        }
        return head;
    }

    private static <T>  void printRandomLinked(LinkedNode<T> head) {
        Objects.requireNonNull(head);
        Console.log("随机指针单向链表打印:");
        while (head != null) {
            Console.log(" {} -> {} ", head.data, head.random != null ? head.random.data : "");
            head = head.next;
            if (head != null) {
                Console.log("  ↓  ");
            }
        }
    }

    public static class LinkedNode<T> {
        public T data;
        private LinkedNode<T> next;
        // 随机指针
        private LinkedNode<T> random;
    }
}
